#include<iostream>
using namespace std;
struct ListNode 
{
 	int val;
 	struct ListNode *next;
 	ListNode(int x) 
        : val(x), next(nullptr) 
    {}
};

class Solution {
public:
    void Reserve(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head->next;
        while (cur)
        {
            ListNode* tmp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = tmp;
        }
    }
    bool isPail(ListNode* head) {
        // write code here
        if (head == nullptr || head->next == nullptr)
            return true;
        ListNode* slow = head;
        int count = 0;
        while (slow)
        {
            slow = slow->next;
            count++;
        }
        if (count % 2)
            return false;
        ListNode* fast = head;
        slow = head;
        while (fast->next && fast->next->next)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        Reserve(slow);
        fast = slow->next;
        ListNode* cur = head;
        bool flag = true;
        while (fast)
        {
            if (cur->val != fast->val)
            {
                flag = false;
                break;
            }
            cur = cur->next;
            fast = fast->next;
        }
        Reserve(slow);
        return flag;
    }
};
int main()
{
    ListNode* head = new ListNode(1);
    ListNode* node = new ListNode(2);
    ListNode* node1 = new ListNode(2);
    ListNode* node2 = new ListNode(1);
    head->next = node;
    node->next = node1;
    node1->next = node2;
    cout << Solution().isPail(head) << endl;
    return 0;
}